package zuochengyun.chapter8;

import java.util.HashMap;
import java.util.Map.Entry;

//未排序数组累加和为给定值的变形
public class ContiguousArray {

	public static void main(String[] args) {
		int[] nums = {0,0,1,0,0,0,1,1};
		ContiguousArray object = new ContiguousArray();
		object.findMaxLength(nums);
	}
	public int findMaxLength(int[] nums) {
		// 找到数组中0和1一样长的最长子数组
		if (nums == null || nums.length <= 0) {
			return 0;
		}
		int[] copy = new int[nums.length];
		// 用来存储和sum最早出现的位置
		HashMap<Integer, Integer> map = new HashMap<>();
		map.put(0, -1); // 当一个数都不加，也就是和为0。由于是j + 1 ... i的和是sum，所以需要加入这条记录
		int sum = 0;
		for (int i = 0; i < nums.length; i++) {
			copy[i] = nums[i] == 0 ? -1 : 1;
			sum += copy[i];
			if (!map.containsKey(sum)) {
				map.put(sum, i);
			}
		}
		sum = 0;
		int maxLength = 0;
		for (int i = 0; i < copy.length; i++) {
			sum += copy[i];
			if (map.containsKey(sum)) {
				maxLength = Math.max(maxLength, i - map.get(sum));
			}
		}
		System.out.println(maxLength);
		return maxLength;
	}
}
